最优包含

题目 最优包含

思路分析

好像是线性dp里的编辑距离的模板

对序列a进行修改使其变成序列b 但这里更复杂 并不是等于序列b 而是包含序列b

代码实现

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
const int N = 1e3+5;
const int INF = 0x3f3f3f3f;
int f[N][N]; // f[i][j] : 修改s中多少字符, s[1~i] 包含 t[1~j]

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s, t;
    cin>>s>>t;
    int n=s.size(),m =t.size();
    s = "#" + s; t = "#" + t;

    memset(f,0x3f,sizeof f);//求最小 初始化inf
    for (int i = 0; i <= n; i++)
        f[i][0] = 0; //s的前i个字符包含t的0个字符需要的代价为0

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (s[i] == t[j]) {
                f[i][j] = f[i - 1][j - 1];
            } else {
                // 如果s[i] != t[j]
                // 要么花费代价1, 使得s[i] == t[j]
                // 要么只使用s的前i-1个字符包含
                f[i][j] = min(f[i - 1][j], f[i - 1][j - 1] + 1);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

同类题型

视频讲解

⬅️ 路径计数 🏠 00-冲刺国赛 ➡️ 排列数